
//#region 岛屿问题

/**200. 岛屿数量-深搜/广搜
 * - 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 
 */
export function numIslands(grid: string[][] = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]): number {
    //深搜与广搜，只需要在最下面的for循环中切换使用即可

    /**地图的宽度 */
    const width = grid[0].length;
    /**地图的高度 */
    const height = grid.length

    /**- 代表四个方向，四行二列数组。
     * - 对于 grid[i][j]：
     * - 下面二维数组第一个元素是代表索引i的运动方向，第二个元素代表索引j的运动方向
     */
    const dir: Array<[number, number]> = [
        [0, 1], //i不动，j向下  ↓
        [1, 0], //i向右，j不动  →
        [-1, 0],//i向左，j不动  ←
        [0, -1] //i不动，j向上  ↑
    ]

    /**访问过的节点数组 */
    const visited = Array.from({ length: height }, () => new Array<boolean>(width).fill(false))

    /**深度优先搜索。将会根据起点的i,j索引，进行深度优先搜索，搜索四个方向，将与其链接的陆地都标记上 true
     * @param _i 起点的i索引
     * @param _j 起点的j索引
     */
    const dfs = (_i: number, _j: number) => {
        for (let i = 0; i < 4; i++) {//遍历四个方向，沿着一个方向走到底才继续下一个方向 
            /**下一个i索引 */
            const nextI = _i + dir[i][0];
            /**下一个j索引 */
            const nextJ = _j + dir[i][1];
            // 越界了，直接跳过
            if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;
            // 没有访问过的 并且 是陆地的
            if (!visited[nextI][nextJ] && grid[nextI][nextJ] == '1') {  //终止条件包含在这里了
                visited[nextI][nextJ] = true;
                dfs(nextI, nextJ);
            }
        }
    }
    /**广度优先搜索。将会根据起点的i,j索引，进行广搜，搜索四个方向，将与其链接的陆地都标记上 true
     * @param _i 起点的i索引
     * @param _j 起点的j索引
     */
    const bfs = (_i: number, _j: number) => {
        /**队列。装元组，第一个元素是这个点的i索引，第二个元素是j索引 */
        const queue: Array<[number, number]> = [[_i, _j]]//初始化放入
        visited[_i][_j] = true; // 只要加入队列，立刻标记
        while (queue.length) {
            const [curI, curJ] = queue.shift()! //取出队头元素
            for (let i = 0; i < 4; i++) {//遍历四个方向，进行广搜
                const nextI = curI + dir[i][0]
                const nextJ = curJ + dir[i][1]
                if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;  // 越界了，直接跳过
                if (!visited[nextI][nextJ] && grid[nextI][nextJ] == '1') {//如果没遍历过，并且是陆地
                    queue.push([nextI, nextJ]);//放入元素
                    visited[nextI][nextJ] = true; // 只要加入队列立刻标记
                }
            }
        }
    }

    /**岛屿计数器 */
    let res = 0
    for (let i = 0; i < height; i++) { //i是与高度相关的，所以这一层遍历高度
        for (let j = 0; j < width; j++) { //j是与宽度相关的，所以这一层遍历宽度

            if (!visited[i][j] && grid[i][j] == '1') { //没访问过，且是陆地的话
                visited[i][j] = true;//标记访问
                res++; // 遇到没访问过的陆地，+1
                dfs(i, j); //深搜 将与其链接的陆地都标记上 true
                // bfs(i, j); //广搜 - 将与其链接的陆地都标记上 true
            }
        }
    }

    return res
}
/**695. 岛屿的最大面积-深搜/广搜
 * - 岛屿的面积是岛上值为 1 的单元格的数目。
 * - 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 * @param grid 
 * @returns 
 */
export function maxAreaOfIsland(grid: number[][] = [
    [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
]): number {
    //深搜与广搜，只需要在最下面的for循环中切换使用即可

    /**宽度 */
    const width = grid[0]?.length || 0
    /**高度 */
    const height = grid.length
    /**- 代表四个方向，四行二列数组。
     * - 对于 grid[i][j]：
     * - 下面二维数组第一个元素是代表索引i的运动方向，第二个元素代表索引j的运动方向
     */
    const dir: Array<[number, number]> = [
        [0, 1], //i不动，j向下  ↓
        [1, 0], //i向右，j不动  →
        [-1, 0],//i向左，j不动  ←
        [0, -1] //i不动，j向上  ↑
    ]
    /**标记访问过的地方，防止重复遍历 */
    const visited = Array.from({ length: height }, () => new Array<boolean>(width).fill(false))
    /**每次遇到陆地的计数器 */
    let count = 0
    /**深搜。给_i,_j 这个坐标所连接的陆地标记上   */
    const dfs = (_i: number, _j: number) => {
        for (let i = 0; i < 4; i++) {
            const nextI = _i + dir[i][0]
            const nextJ = _j + dir[i][1]
            if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue//越界
            if (!visited[nextI][nextJ] && grid[nextI][nextJ]) {//没访问过且是陆地
                visited[nextI][nextJ] = true
                count++
                dfs(nextI, nextJ)
            }
        }
    }
    /**广搜 */
    const bfs = (_i: number, _j: number) => {
        const queue: Array<[number, number]> = []
        queue.push([_i, _j])//初始化中心点
        visited[_i][_j] = true //放入了就标记为true
        while (queue.length) {
            const [curI, curJ] = queue.shift()!
            for (let i = 0; i < 4; i++) {
                const nextI = curI + dir[i][0]
                const nextJ = curJ + dir[i][1]
                if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;  // 越界了，直接跳过
                if (!visited[nextI][nextJ] && grid[nextI][nextJ]) {//如果没遍历过，并且是陆地
                    queue.push([nextI, nextJ]);//放入元素
                    count++
                    visited[nextI][nextJ] = true; // 只要加入队列立刻标记
                }
            }
        }
    }
    /**最大面积 */
    let max = 0
    //遍历这个地图，遇到陆地就调用dfs/bfs进行“感染”
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (!visited[i][j] && grid[i][j]) {//没遍历过，且是陆地
                count = 1 //当前这就是一个陆地
                visited[i][j] = true
                dfs(i, j)//广搜 - 把这个陆地周围的地方标记上 
                // dfs(i, j)//深搜- 把这个陆地周围的地方标记上 
                max = Math.max(max, count)
            }
        }
    }
    return max
}
/**1020. 飞地的数量-深搜/广搜
 * - 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
 * - 实际上就是判断有几个陆地没有和边界接壤。
 */
export function numEnclaves(grid: number[][] = [
    [0, 0, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
]): number {
    //注意，此题问的不是岛屿的个数，是陆地的个数

    /**地图的宽度 */
    const width = grid[0]?.length || 0
    /**地图的高度 */
    const height = grid.length
    /**- 代表四个方向，四行二列数组。
     * - 对于 grid[i][j]：
     * - 下面二维数组第一个元素是代表索引i的运动方向，第二个元素代表索引j的运动方向
     */
    const dir: Array<[number, number]> = [
        [0, 1], //i不动，j向下  ↓
        [1, 0], //i向右，j不动  →
        [-1, 0],//i向左，j不动  ←
        [0, -1] //i不动，j向上  ↑
    ]
    /**统计符合题目要求的陆地空格数量 */
    let count = 0;

    /**深搜，把遇到的陆地变成海洋 */
    const dfs = (_i: number, _j: number) => {
        grid[_i][_j] = 0 //改为海洋
        count++;
        for (let i = 0; i < dir.length; i++) {
            const nextI = _i + dir[i][0];
            const nextJ = _j + dir[i][1];
            if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;// 越界了，直接跳过 
            if (grid[nextI][nextJ] == 1) {  // 是陆地的  //终止条件包含在这里了 
                dfs(nextI, nextJ);
            }
        }
    }
    /**广搜，把遇到的陆地变成海洋 */
    const bfs = (_i: number, _j: number) => {
        const queue: Array<[number, number]> = []
        queue.push([_i, _j])
        //在放入的时候计数，并变为海洋
        count++
        grid[_i][_j] = 0
        while (queue.length) {
            const [curI, curJ] = queue.shift()!
            //遍历四个方向，进行广搜
            for (let i = 0; i < 4; i++) {
                const nextI = curI + dir[i][0];
                const nextJ = curJ + dir[i][1];
                if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;  // 越界了，直接跳过
                if (grid[nextI][nextJ] == 1) {
                    queue.push([nextI, nextJ])
                    //在放入的时候计数，并变为海洋
                    count++
                    grid[nextI][nextJ] = 0
                }
            }
        }
    }


    //想切换使用bfs或dfs，就把下面全部的函数名改一下即可

    //遍历四个侧边，把 与边界接壤的陆地 全部变成海洋
    for (let i = 0; i < height; i++) { //遍历左侧右侧
        if (grid[i][0] == 1) dfs(i, 0);
        if (grid[i][width - 1] == 1) dfs(i, width - 1);
    }
    for (let j = 0; j < width; j++) { //遍历上侧下侧
        if (grid[0][j] == 1) dfs(0, j);
        if (grid[height - 1][j] == 1) dfs(height - 1, j,);
    }

    //最后再遍历一次地图，看看一共几个陆地
    count = 0

    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (grid[i][j] == 1) dfs(i, j);
        }
    }

    return count
}
/**130. 被围绕的区域-深搜/广搜
 * - 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 */
export function solve(board: string[][] = [
    ["X", "X", "X", "X"],
    ["X", "O", "O", "X"],
    ["X", "X", "O", "X"],
    ["X", "O", "X", "X"]
]): void {
    //思路：这题和 1020飞地的数量 刚好相反，是要把边缘的保留，四面环海的填充
    //      先遍历一遍，把接壤边界的全部变为 'A' （使用深搜广搜）
    //      然后两个for遍历第二遍，把 'O' 改为 'X' ， 把 'A' 改为 'O'

    /**地图的宽度 */
    const width = board[0]?.length || 0
    /**地图的高度 */
    const height = board.length
    /**- 代表四个方向，四行二列数组。
     * - 对于 grid[i][j]：
     * - 下面二维数组第一个元素是代表索引i的运动方向，第二个元素代表索引j的运动方向
     */
    const dir: Array<[number, number]> = [
        [0, 1], //i不动，j向下  ↓
        [1, 0], //i向右，j不动  →
        [-1, 0],//i向左，j不动  ←
        [0, -1] //i不动，j向上  ↑
    ]
    /**深搜，把O变为A */
    const dfs = (_i: number, _j: number) => {
        board[_i][_j] = 'A' //把O标记为A
        for (let i = 0; i < dir.length; i++) {
            const nextI = _i + dir[i][0]
            const nextJ = _j + dir[i][1]
            if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;// 越界了，直接跳过 
            if (board[nextI][nextJ] == 'X' || board[nextI][nextJ] == 'A') continue;//如果已经是X或者A了，就不继续下去了
            dfs(nextI, nextJ);
        }
    }
    /**广搜，把O变为A */
    const bfs = (_i: number, _j: number) => {
        const queue: Array<[number, number]> = []
        queue.push([_i, _j])//初始化
        board[_i][_j] = 'A' //一旦放入队列就记得把它变成A
        while (queue.length) {
            const [curI, curJ] = queue.shift()!
            for (let i = 0; i < dir.length; i++) {
                const nextI = curI + dir[i][0];
                const nextJ = curJ + dir[i][1];
                if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;  // 越界了，直接跳过 
                if (board[nextI][nextJ] === 'A' || board[nextI][nextJ] === 'X') continue  //如果不是O就跳过
                queue.push([nextI, nextJ])//初始化
                board[nextI][nextJ] = 'A' //一旦放入队列就记得把它变成A   
            }
        }
    }
    //遍历四个侧边，把 与边界接壤的O 全部变成A
    for (let i = 0; i < height; i++) { //遍历左侧右侧
        if (board[i][0] == 'O') dfs(i, 0);
        if (board[i][width - 1] == 'O') dfs(i, width - 1);
    }
    for (let j = 0; j < width; j++) { //遍历上侧下侧
        if (board[0][j] == 'O') dfs(0, j);
        if (board[height - 1][j] == 'O') dfs(height - 1, j,);
    }
    //然后再遍历一次，把A改O，把O改X  （这里不用深搜/广搜了）
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            if (board[i][j] == 'A') board[i][j] = 'O';
        }
    }
    console.log(board);



}
/**417. 太平洋大西洋水流问题-深搜（广搜没写）
 * - 有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界
 * - 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
 * - 岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
 * - 返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
 * - 省流： 雨水从高往低走，寻找哪个点能够同时到达太平洋和大西洋，返回坐标数组
 */
export function pacificAtlantic(heights: number[][] = [
    [1, 2, 2, 3, 5],
    [3, 2, 3, 4, 4],
    [2, 4, 5, 3, 1],
    [6, 7, 1, 4, 5],
    [5, 1, 1, 2, 4]
]): number[][] {
    // 题目的意思就是寻找，哪个点能够同时到达太平洋和大西洋。
    // 思路：分别从太平洋和大西洋的接壤节点逆流而上并进行标记，最后再看看哪个点同时有太平洋和大西洋的标记
    /**地图的宽度 */
    const width = heights[0]?.length || 0
    /**地图的高度 */
    const height = heights.length
    /**- 代表四个方向，四行二列数组。
     * - 对于 grid[i][j]：
     * - 下面二维数组第一个元素是代表索引i的运动方向，第二个元素代表索引j的运动方向
     */
    const dir: Array<[number, number]> = [
        [0, 1], //i不动，j向下  ↓
        [1, 0], //i向右，j不动  →
        [-1, 0],//i向左，j不动  ←
        [0, -1] //i不动，j向上  ↑
    ]
    /**0: 无标记  1：太平洋标记  2：大西洋标记  3：都标记 */
    type mark = 0 | 1 | 2 | 3
    const visited = Array.from({ length: height }, () => new Array<mark>(width).fill(0))
    /**深搜 */
    const dfs = (_i: number, _j: number, mark: mark) => {
        if (visited[_i][_j] === 0) {//如果什么都没标记过
            visited[_i][_j] = mark
        } else if (visited[_i][_j] === mark || visited[_i][_j] === 3) {//如果当前点位，已经是目标标记了，或者已经是都标记了，就不做事
            return
        } else {//剩下的就是标记为3
            visited[_i][_j] = 3
        }
        for (let i = 0; i < dir.length; i++) {
            const nextI = _i + dir[i][0]
            const nextJ = _j + dir[i][1]
            if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;// 越界了，直接跳过 
            if (heights[nextI][nextJ] >= heights[_i][_j]) { //逆流而上，寻找符合的路线
                dfs(nextI, nextJ, mark)
            }
        }
    }
    for (let i = 0; i < height; i++) {//遍历左右两侧
        dfs(i, 0, 1) //左侧太平洋
        dfs(i, width - 1, 2) //右侧大西洋
    }
    for (let j = 0; j < width; j++) {//遍历上下两侧
        dfs(0, j, 1) //上侧太平洋
        dfs(height - 1, j, 2) //下侧大西洋
    }
    let res: number[][] = []
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (visited[i][j] === 3) {
                res.push([i, j])
            }
        }
    }
    return res
}
/**827. 最大人工岛-深搜（广搜没写）
 * - 给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
 * - 返回执行此操作后，grid 中最大的岛屿面积是多少？
 */
export function largestIsland(grid: number[][] = [[1, 0], [0, 1]]): number {
    //思路: 先遍历原地图，给每个岛屿编号并求面积，存放在map中
    //      然后遍历每个节点，尝试把0改成1，并计算改了合并周围之后的最大面积(前面记录的map就在这里使用)

    console.log(grid);
    /**地图的宽度 */
    const width = grid[0]?.length || 0
    /**地图的高度 */
    const height = grid.length
    /**- 代表四个方向，四行二列数组。
     * - 对于 grid[i][j]：
     * - 下面二维数组第一个元素是代表索引i的运动方向，第二个元素代表索引j的运动方向
     */
    const dir: Array<[number, number]> = [
        [0, 1], //i不动，j向下  ↓
        [1, 0], //i向右，j不动  →
        [-1, 0],//i向左，j不动  ←
        [0, -1] //i不动，j向上  ↑
    ]

    /**当前面积 */
    let count = 0
    /**深搜，找到相连的所有陆地。记录映射关系，并且给遍历过的岛屿修改编号 */
    const dfs = (_i: number, _j: number, mark: number) => {
        if (grid[_i][_j] !== 1) return; // 终止条件：访问过的节点 或者 遇到海水
        grid[_i][_j] = mark//修改编号
        count++//记录面积  

        for (let i = 0; i < dir.length; i++) {
            const nextI = _i + dir[i][0]
            const nextJ = _j + dir[i][1]
            if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) continue;// 越界了，直接跳过  
            dfs(nextI, nextJ, mark)//把相连的陆地全部标记上 
        }
    }

    /**是否全是陆地 */
    let isAllGrid = true
    /**编号, 从2开始递增 */
    let mark = 2
    /**使用哈希表记录 原始的 岛屿编号 与 岛屿面积 的映射关系 */
    const map: Map<number, number> = new Map()
    //遍历所有节点，建立映射关系
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (grid[i][j] == 0 && isAllGrid) isAllGrid = false;
            if (grid[i][j] == 1) { //如果当前是陆地 
                count = 0;//重新计算新一轮的面积
                dfs(i, j, mark); // 将与其链接的陆地都标记上编号
                map.set(mark, count)  // 记录这一个岛屿的面积
                mark++; // 记录下一个岛屿编号
            }
        }
    }
    if (isAllGrid) return height * width; // 如果都是陆地，返回全面积
    console.log(map);
    let res = 0
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            /**填海造路之后的面积 */
            let count = 1
            /**已经使用过的编号 */
            let numberMap = new Map<number, boolean>()
            if (grid[i][j] === 0) {//如果是海洋，就尝试改为陆地
                //看看四周有没有岛屿，有的话就合并
                for (let k = 0; k < dir.length; k++) {
                    let neari = i + dir[k][1]; // 计算相邻坐标
                    let nearj = j + dir[k][0];
                    if (neari < 0 || neari >= height || nearj < 0 || nearj >= width) continue;//越界
                    const num = grid[neari][nearj] //当前岛屿编号
                    if (num === 0 || numberMap.has(num)) continue//如果已经用过，或者是海洋，就不用了
                    count += (map.get(num) || 0) //计算面积
                    numberMap.set(num, true)//标记为使用过的编号
                }
            }
            res = Math.max(res, count)
        }
    }
    return res
}
/**463. 岛屿的周长-普通
 * - 0代表水域，1代表陆地
 * - 地图中只有一个岛屿，求这个岛屿的周长
 */
export function islandPerimeter(grid: number[][] = [
    [0, 1, 0, 0],
    [1, 1, 1, 0],
    [0, 1, 0, 0],
    [1, 1, 0, 0]
]): number {
    //这题用不上深搜和广搜，因为只有一个岛屿。遍历所有格子，一旦发现是陆地，就看看四周，发现一格水域则周长+1，发现边界也周长+1
    /**地图的宽度 */
    const width = grid[0].length;
    /**地图的高度 */
    const height = grid.length
    /**- 代表四个方向，四行二列数组。
     * - 对于 grid[i][j]：
     * - 下面二维数组第一个元素是代表索引i的运动方向，第二个元素代表索引j的运动方向
     */
    const dir: Array<[number, number]> = [
        [0, 1], //i不动，j向下  ↓
        [1, 0], //i向右，j不动  →
        [-1, 0],//i向左，j不动  ←
        [0, -1] //i不动，j向上  ↑
    ]
    /**面积 */
    let count = 0
    for (let i = 0; i < height; i++) {
        for (let j = 0; j < width; j++) {
            if (grid[i][j] === 1) {//如果是岛屿
                for (let k = 0; k < dir.length; k++) {
                    const nextI = i + dir[k][0];
                    const nextJ = j + dir[k][1];
                    if (nextI < 0 || nextI >= height || nextJ < 0 || nextJ >= width) {//发现边界
                        count++
                        continue
                    }
                    if (grid[nextI][nextJ] === 0) {//发现水域
                        count++
                    }
                }

            }
        }
    }
    return count
}

//#endregion

